#include <iostream>
using namespace std;
typedef struct Node
{
	int val, data;
	int h;
	int bf;
	Node *left, *right;
}Node; 
class AvlTree
{
private:
	Node *root;
public:
	void Init()
	{
		root = NULL;
	}
	int Height(Node *T)
	{
		if (T == NULL)
			return 0;
		return T->h;
	}
	int Bf(Node *T)
	{
		if (T->left == T->right)
			return 0;
		if (T->left == NULL)
			return -(T->right->h);
		if (T->right == NULL)
			return T->left->h;
		return (T->left->h) - (T->right->h);
	}
	Node *LL_rotate(Node *T)
	{
		Node *B = T->left;
		T->left = B->right;
		B->right = T;
		T->h = max(Height(T->left),Height(T->right)) + 1;
		B->h = max(Height(B->left),Height(T->right)) + 1;
		T->bf = Bf(T);
		B->bf = Bf(B);
		return B;
	}
	Node *RR_rotate(Node *T)
	{
		Node *B = T->right;
		T->right = B->left;
		B->left = T;
		T->h = max(Height(T->left), Height(T->right)) + 1;
		B->h = max(Height(B->left), Height(T->right)) + 1;
		T->bf = Bf(T);
		B->bf = Bf(B);
		return B;
	}
	Node *LR_rotate(Node *T)
	{
		T->left = RR_rotate(T->left);
		T = LL_rotate(T);
		return T;
	}
	Node *RL_rotate(Node *T)
	{
		T->right = LL_rotate(T->right);
		T = RR_rotate(T);
		return T;
	}
	void Insert(int v, int e)
	{
		Insert(root, v, e);
	}
	void Insert(Node *&T, int v, int e)
	{
		if (T == NULL)
		{
			T = (Node *)malloc(sizeof(Node));
			T->h = 1;
			T->bf = 0;
			T->val = v;
			T->date = e;
			T->left = T->right = NULL;
			return; 
		}
		if (e < T->date)
			Insert(T->left, v, e);
		else
			Insert(T->right, v, e);
		T->h = max(Height(T->left), Height(T->right)) + 1;
		T->bf = Bf(T);
		if (T->bf > 1 || T->bf < -1)
		{
			if (T->bf > 1 && T->left->bf > 0)
				T = LL_rotate(T);
			if (T->bf < -1 && T->right->bf < 0)
				T = RR_rotate(T);
			if (T->bf > 1 && T->left->bf < 0)
				T = LR_rotate(T);
			if (T->bf < -1 && T->right > 0)
				T = RL_rotate(T);
		}
	}
	void Find(int flag)
	{
		if (root == NULL)
		{
			printf("0\n");
			return;
		}
		Node *temp = root;
		if (flag)
			while (temp->right)
				temp = temp->right;
		else
			while (temp->left)
				temp = temp->left;
		printf("%d\n", temp->val);
		Delete(root, temp->data);
	}
	void Delete(Node *&T, int e)
	{
		if (T == NULL)
			return;
		if (e < T->data)
			Delete(T->left, e);
		else if (e > T->data)
			Delete(T->right, e);
		else
		{
			if (T->left && T->right)
			{
				Node *temp = T->left;
				while (temp->right)
					temp = temp->right;
				T->val = temp->val;
				T->data = temp->data;
				Delete(T->left, temp->data);
			}
			else
			{
				Node *temp = T;
				if (T->left)
					T = T->left;
				else if (T->right)
					T = T->right;
				else
				{
					free(T);
					T = NULL;
				}
				if (T)
					free(temp);
				return;
			}
		}
		T->h = max(Height(T->left), Height(T->right)) + 1;
		T->bf = Bf(T);
		if (T->bf > 1 || T->bf < -1)
		{
			if (T->bf > 1 && T->left->bf > 0)
				T = LL_rotate(T);
			if (T->bf < -1 && T->right->bf < 0)
				T = RR_rotate(T);
			if (T->bf > 1 && T->left->bf < 0)
				T = LR_rotate(T);
			if (T->bf < -1 &&T->right > 0)
				T = RL_rotate(T);
		}
	}
	void Free()
	{
		FreeNode(root);
	}
	voide FreeNode(Node *T)
	{
		if (T == NULL)
			return;
		if (T->right)
			FreeNode(T->right);
		if (T->left)
			FreeNode(T->left);
		free(T);
	}
};
AvlTree T;
int main()
{
	T.Init();
	int op;
	while (~scanf("%d",&op) && op)
	{
		if (op == 1)
		{
			int v, e;
			scanf("%d%d", &v, &e);
			T.Insert(v, e);
		}
		if (op == 2)
			T.Find(1);
		if (op == 3)
			T.Find(0);
	}
	T.Free();
	return 0;
}
